package sort

import (
//    "fmt"
//    "sort"
)

var QSThreshold int = 50

func (a Array) swap(i, j int) {
    a[i], a[j] = a[j], a[i]
}

func Partition(a Array, pivot_index int) (l,m,r int) {
    pivot := a[pivot_index]
    l,m,r = 0,0,a.Len()-1
    a.swap(pivot_index, r)
    r--
    for ; m<=r; m++{
        if a[m] < pivot {
            a.swap(m, l)
            l++
        } else if a[m] > pivot {
            a.swap(m, r)
            r--
            m--
        }
        //fmt.Println(a, l, m, r)
    }
    a.swap(a.Len()-1, m)
    r++
    return
}

func ParallelQuickSort(a Array, resp chan int) {
    //fmt.Println("ParallelQuickSort on", a)
    if a.Len() < QSThreshold {
        //fmt.Println("Calling InsertionSort")
        a.InsertionSort()
        resp <- 1
        return
    }
    _, index := Median(a)
    //fmt.Println("Pivot = ", pivot, a)
    left, _, right := Partition(a, index)
    //fmt.Println("After partition by ", index, pivot, a)

    wait := make(chan int, 2)
    go ParallelQuickSort(a[:left], wait)
    ParallelQuickSort(a[right:], wait)
    <-wait
    <-wait
    //fmt.Println(a)
    resp <- 1
}


func SerialQuickSort(a Array) {
    if a.Len() < QSThreshold {
        a.InsertionSort()
        return
    }
    _, index := Median(a)
    left, _, right := Partition(a, index)

    SerialQuickSort(a[:left])
    SerialQuickSort(a[right:])
}
